package varvelworld.algorithm.DuplicationFinding;

import java.util.ArrayList;
import java.util.List;

public class Tree implements IDuplicationFinding {

    @Override
    public List<Long> execute(long[] a) {
        List<Long> result = new ArrayList<Long>();
        Node root = new Node(a[0], 1);
        for(int i = 1; i < a.length; i++){
            Node n = root;
            while(true){
                if(a[i] == n.v){
                    n.s++;
                    if(n.s == 2){
                        result.add(n.v);
                    }
                    break;
                }else if(a[i] < n.v){
                    if(n.left == null){
                        n.left = new Node(a[i], 1);
                        break;
                    }
                    else{
                        n = n.left;
                    }
                }else{
                    if(n.right == null){
                        n.right = new Node(a[i], 1);
                        break;
                    }
                    else{
                        n = n.right;
                    }
                }
            }
        }
        return result;
    }

    static class Node{
        long v;
        int s;
        Node left;
        Node right;
        public Node(long v, int s){
            super();
            this.v = v;
            this.s = s;
        }
        
    }
}
